<?xml version="1.0"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" lang="en" xml:lang="en">
	<head>
		<title>JavaScript Hashtable</title>
		<meta http-equiv="content-type" content="text/html; charset=iso-8859-1" />
		<meta name="author" content="Tim Down - tim@timdown.co.uk" />
		<meta name="keywords" content="hashtable, hash, JavaScript, DHTML, hashmap" />
		<meta name="description" content="jshashtable, a JavaScript hash table implementation" />
		<meta name="robots" content="all" />
		<link rel="stylesheet" type="text/css" media="screen,print" href="main.css" title="Default" />
	</head>
	<body>
        <div id="container" class="nonav">
            <div id="header">
                <h1>jshashtable 2.0</h1>
                <div id="nav">
                    <span class="navitem">home</span>
                    | <a class="navitem" href="http://code.google.com/p/jshashtable/downloads/list" target="_blank"
                         title="Download (opens in new window)">download</a>
                    | <a class="navitem" href="http://www.timdown.co.uk/jshashtable" target="_blank">website</a>
                    | <a class="navitem" href="http://www.timdown.co.uk" target="_blank">timdown.co.uk</a>
                </div>
            </div>
            <div id="content">
                <h1>jshashtable 2.0</h1>
                <div id="toc">
                    <h2>Contents</h2>
                    <ul>
                        <li><a href="#intro">Introduction</a></li>
                        <li><a href="#setup">Set-up</a></li>
                        <li><a href="#usage">Usage</a></li>
                        <li><a href="#api">Public API</a></li>
                    </ul>
                </div>
                <div id="intro">
                    <h2>Introduction</h2>
                    <p>
                        jshashtable is a JavaScript implementation of a hash table. It associates objects ("keys") with
                        other objects ("values"). Each key is associated with precisely one value.
                    </p>
                    <p>
                        Version 2.0 of jshashtable features significant performance improvements over version 1.0
                        (typically 200% faster for <code>put</code> and <code>get</code> operations) and adds a few new
                        methods: <code>clone()</code>, <code>putAll()</code>, <code>entries()</code> and
                        <code>each()</code>.
                    </p>
                    <p class="linktotop">
                        <a href="#container">Top</a>
                    </p>
                </div>
                <div id="setup">
                    <h2>Set-up</h2>
                    <ol>
                        <li>
                            <h3>Download the code</h3>
                            <p>
                                <strong><a href="http://code.google.com/p/jshashtable/downloads/list" target="_blank"
                                           title="Download (opens in new window)">Download jshashtable</a></strong>.
                                You can download a compressed or uncompressed version of <code>jshashtable.js</code>
                                which are functionally identical or a zip containing this document and both JavaScript
                                files.
                            </p>
                        </li>
                        <li>
                            <h3>Include jshashtable in your page</h3>
                            <p>
                                Include <code>jshashtable.js</code> in a script tag in your page. This file creates one
                                object in the global scope, which is <code>Hashtable</code>.
                            </p>
                        </li>
                        <li>
                            <h3>Create your hash table</h3>
                            <p>
                                Create your hash table, as in the example below. Any non-null JavaScript object can be
                                used as a key or a value.
                            </p>
                    <pre class="code">
&lt;script type="text/javascript" src="jshashtable.js"&gt;&lt;/script&gt;
&lt;script type="text/javascript"&gt;
    var typesHash = new Hashtable();

    typesHash.put("A string", "string");
    typesHash.put(1, "number");

    var o = new Object();
    typesHash.put(o, "object");

    alert( typesHash.get(o) ); // "object"
&lt;/script&gt;
</pre>
                        </li>
                    </ol>
                    <p class="linktotop">
                        <a href="#container">Top</a>
                    </p>
                </div>
                <div id="usage">
                    <h2>Usage</h2>
                    <p>
                        jshashtable is a JavaScript implementation of a hash table. It associates objects ("keys") with
                        other objects ("values"). Each key is associated with precisely one value.
                    </p>
                    <p>
                        The code is contained in one JavaScript file, which creates a single constructor function called
                        <code>Hashtable</code> in the global scope.
                    </p>
                    <h3>Doesn't JavaScript already do this?</h3>
                    <p>
                        No, although JavaScript's built-in objects do provide this functionality using the square
                        brackets notation for properties, <strong>provided your keys are strings or numbers</strong>:
                    </p>
                    <pre class="code">
var key = "A key";
var o = new Object();
o[key] = 1;
</pre>
                    <p>
                        However, it is often desirable to use other kinds of objects as keys. JavaScript doesn't
                        complain if you try to use objects other than strings and numbers inside square brackets;
                        indeed, it superficially looks like this kind of association works for any object:
                    </p>
                    <pre class="code">
var key = new Object();
var o = new Object();
o[key] = "First";
alert( o[key] ); // Alerts "First"
</pre>
                    <p>
                        It doesn't take much effort to discover the flaw in this approach:
                    </p>
                    <pre class="code">
var key1 = new Object();
var key2 = new Object();
var o = new Object();
o[key1] = "First";
o[key2] = "Second";
alert( o[key1] ); // Alerts "Second", not "First"
</pre>
                    <p>
                        The reason for this is that JavaScript silently calls <code>toString()</code> on the object
                        being passed in as the key and uses the result as the property name. In the example above,
                        <code>key1</code> and <code>key2</code> both become "[object Object]", hence the second
                        assignment simply replaces the original value of the property "[object Object]".
                    </p>
                    <p>
                        With jshashtable, any object can be used as the key:
                    </p>
                    <pre class="code">
var key1 = new Object();
var key2 = new Object();
var h = new Hashtable();
h.put(key1, "First");
h.put(key2, "Second");
alert( h.get(key1) ); // Alerts "First"
alert( h.get(key2) ); // Alerts "Second"
</pre>
                    <p>
                        The above examples shows use of <code>put()</code> to add a key/value pair to the hash table and
                        <code>get()</code> to retrieve a value. If a value already exists in the hash table for
                        the key used, it is replaced with the new value.
                    </p>
                    <h3>Equality</h3>
                    <p>
                        This is all very well but there is a drawback. Imagine you have a hash table of colour values at
                        various different positions on the screen. Each position on the screen is represented by a
                        <code>Point</code> object, which has properties <code>x</code> and <code>y</code>, representing
                        the x and y coordinates of the point on the screen.
                    </p>
                    <pre class="code">
function Point(x, y) {
    this.x = x;
    this.y = y;
}

var coloursForPoints = new Hashtable();

function getColourAt(x, y) {
    var point = new Point(x, y);
    return coloursForPoints.get(point);
}

coloursForPoints.put( new Point(1, 2), "green" );

alert( getColourAt(1, 2) ); // Alerts null
</pre>
                    <p>
                        Why do we get <code>null</code>? Because the <code>Point</code> object that gets created in
                        <code>getColourAt</code> is not the self same object as the original <code>Point</code> that got
                        used as key in the <code>coloursForPoints</code> hash table. This is clearly not the ideal
                        behaviour - any two <code>Point</code> objects with the same x and y values are to all intents
                        and purposes the same thing. What we need is a way of defining when two objects are equal. By
                        default, jshashtable uses the strict equals (<code>===</code>) operator in JavaScript. However,
                        if one of the objects being compared has an <code>equals</code> method, it will use that
                        instead. We can implement an <code>equals</code> method in the above example to get the
                        behaviour we want:
                    </p>
                    <pre class="code">
function Point(x, y) {
    this.x = x;
    this.y = y;
}

<span class="new">Point.prototype.equals = function(obj) {
    return (obj instanceof Point) &amp;&amp;
        (obj.x === this.x) &amp;&amp;
        (obj.y === this.y);
};</span>

var coloursForPoints = new Hashtable();

function getColourAt(x, y) {
    var point = new Point(x, y);
    return coloursForPoints.get(point);
}

coloursForPoints.put( new Point(1, 2), "green" );

alert( getColourAt(1, 2) ); // <span class="new">Alerts "green"</span>
</pre>
                    <h3>Hash codes</h3>
                    <p>
                        This works but is still not quite ideal. Internally, jshashtable stores key/values pairs in
                        arrays, called <em>buckets</em>. When <code>put</code> is called, jshashtable converts the key
                        into a <em>hash code</em>, and stores the key/value pair in the bucket for that particular hash
                        code. A hash code in jshashtable is a string so that the buckets themselves can be associated
                        with hash codes using the JavaScript's built-in square bracket property notation. When
                        <code>get</code> is called, jshashtable finds the correct bucket for the key it's looking for
                        and then searches the contents of that bucket for that key. Since the process of locating the
                        correct bucket is massively faster than searching through a bucket's contents, it is more
                        efficient to have as many buckets as possible containing the least possible number of items
                        (ideally one). My tests have shown that for a hash table with 1000 elements, it is around
                        <strong>70 times faster</strong> to replace or retrieve a value if each key has a unique hash
                        code than if each key had the same hash code (tested using objects with a very simple
                        <code>hashCode</code> method). For 10000 elements, it's closer to 300 times faster. So,
                        generating meaningful hash codes for keys makes the hash table much more efficient.
                    </p>
                    <p>
                        jshashtable generates a hash code for an object by checking to see if it has a
                        <code>hashCode</code> method and using that if it exists. Otherwise it calls
                        <code>toString</code> on the object, like JavaScript's built-in square bracket property accessor
                        does. In the above example, <code>Point</code> has no <code>hashCode</code> method, so every
                        point placed in <code>coloursForPoints</code> goes into the "[object Object]" bucket, which is
                        very inefficient, particularly with a larger number of points. What would be better would be to
                        implement a <code>hashCode</code> method on <code>Point</code> that returns a different value
                        for every distinct point but the same value for equal points (this is very important: objects
                        that are considered equal according to their <code>equals</code> method must return the same
                        hash code). Something like the following would be good:
                    </p>
                    <pre class="code">
Point.prototype.hashCode = function(obj) {
    return "Point:" + this.x + "," + this.y;
};
</pre>
                    <p>
                        So for our example point, this returns "Point:1,2", for any <code>Point</code> object with x
                        and y coordinates of 1 and 2 respectively. Every point will therefore go in its own bucket and
                        the hash table is efficient.
                    </p>
                    <p>
                        The "Point" at the start is there to distinguish points from any other similar object that may
                        have x and y coordinates and potentially have the same hash code. Note that even if a non-Point
                        object did return a hash code of "Point:1,2", the hash table would still work fine, since the
                        non-Point object would fail the equality test when searching through the "Point:1,2" bucket.
                    </p>
                    <p>
                        If don't want to violate the keys of your hash table by giving them extra methods like
                        <code>equals</code> and <code>hashCode</code>, you can instead pass in functions into the
                        <code>Hashtable</code> constructor to generate hash codes and test key equality. The hash code
                        generator function is passed an object and should return a hash code for that object and the
                        equality function is passed two objects and should return a boolean value representing whether
                        the two objects are equal. This also has the advantage of improving performance, since the hash
                        table does not have to check for the existence of <code>equals</code> and <code>hashCode</code>
                        methods on every key object.
                    </p>
                    <p>
                        For a hash table where you knew in advance that all the keys would be <code>Point</code>
                        objects, the previous example could be rewritten to be more efficient as follows:
                    </p>
                    <pre class="code">
function Point(x, y) {
    this.x = x;
    this.y = y;
}

<span class="new">function hashPoint(p) {
    return "Point:" + p.x + "," + p.y;
}

function pointsEqual(p1, p2) {
    return p1.x === p2.x && p1.y === p2.y;
}

var coloursForPoints = new Hashtable(hashPoint, pointsEqual);</span>

function getColourAt(x, y) {
    var point = new Point(x, y);
    return coloursForPoints.get(point);
}

coloursForPoints.put( new Point(1, 2), "green" );

alert( getColourAt(1, 2) ); <span class="new">// Alerts green</span>
</pre>
                    <p class="linktotop">
                        <a href="#container">Top</a>
                    </p>
                </div>
                <div id="api">
                    <h2>Public API</h2>
                    <h4>Constructors</h4>
                    <ul class="propertieslist">
                        <li class="method">
                            <div class="methodsignature">
                                <code><strong>Hashtable</strong>()</code>
                            </div>
                            <p>
                                Creates a new, empty hash table.
                            </p>
                        </li>
                        <li class="method">
                            <div class="methodsignature">
                                <code><strong>Hashtable</strong>(Function <em>hashingFunction</em>, Function
                                    <em>equalityFunction</em>)</code>
                            </div>
                            <div class="paramsheading">Parameters:</div>
                            <ul class="params">
                                <li class="param">
                                    <code class="paramname">hashingFunction</code>
                                    <div>
                                        A function that provides hash codes for keys placed in the hash table.
                                        It is passed the object to be hashed as its only parameter. If not provided,
                                        the hash table checks whether the object has a <code>hashCode</code> method,
                                        and if not, calls <code>toString</code> on the object.
                                    </div>
                                </li>
                                <li class="param">
                                    <code class="paramname">equalityFunction</code>
                                    <div>
                                        A function that checks for equality between two keys with the same hash code.
                                        Two keys that are considered equal will map to the same value in the hash table.
                                        This function is passed the two objects to be compared as its parameters.
                                        If not provided, the hash table checks whether either object being compared has
                                        an <code>equals</code> method, and if not, compares the objects using the
                                        <code>===</code>operator.
                                    </div>
                                </li>
                            </ul>
                        </li>
                    </ul>
                    <h4>Methods</h4>
                    <ul class="propertieslist">
                        <li class="method">
                            <div class="methodsignature"><code>void <strong>put</strong>(Object <em>key</em>, Object
                                <em>value</em>)</code></div>
                            <div class="summary">
                                <p class="new">Updated in version 2.0: now returns previous value associated with the
                                    key</p>
                                <p>
                                    Sets the value associated with the key supplied. If the hash table already contains
                                    the key then the old value is overwritten and the old
                                    value is returned, otherwise <code>null</code> is returned.
                                </p>
                            </div>
                        </li>
                        <li class="method">
                            <div class="methodsignature"><code>void <strong>putAll</strong>(Hashtable
                                <em>hashtable</em>[, Function <em>conflictCallback</em>])</code></div>
                            <div class="summary">
                                <p class="new">New in version 2.0</p>
                                <p>
                                    Adds all entries from the supplied hash table to this hash table. For any key in the
                                    supplied hash table for which an entry already exists in this hash table, the
                                    optional callback function <code>conflictCallback</code> is called to resolve the
                                    conflict. This function should accept three parameters:
                                </p>
                                <ul>
                                    <li><code>key</code>: the key for the conflicting entry;</li>
                                    <li><code>thisValue</code>: the current value for this key in the current hash
                                        table;</li>
                                    <li><code>value</code>: the value for this key in the hash table supplied.</li>
                                </ul>
                                <p>
                                    The value returned by the callback function will be used as the value for the new
                                    entry in the current hash table. If no callback function is supplied, the existing
                                    value in the current hash table will be overwritten by the value in the hash table
                                    supplied.
                                </p>
                            </div>
                        </li>
                        <li class="method">
                            <div class="methodsignature"><code>void <strong>get</strong>(Object
                                <em>key</em>)</code></div>
                            <div class="summary">
                                <p>
                                    Returns the value associated with the key supplied, or <code>null</code> if no value
                                    is found for that key.
                                </p>
                            </div>
                        </li>
                        <li class="method">
                            <div class="methodsignature"><code>Boolean <strong>containsKey</strong>(Object
                                <em>key</em>)</code></div>
                            <div class="summary">
                                <p>
                                    Returns whether the hash table contains the specified key.
                                </p>
                            </div>
                        </li>
                        <li class="method">
                            <div class="methodsignature"><code>Boolean <strong>containsValue</strong>(Object
                                <em>value</em>)</code></div>
                            <div class="summary">
                                <p>
                                    Returns whether the hash table contains the specified value.
                                </p>
                            </div>
                        </li>
                        <li class="method">
                            <div class="methodsignature"><code>void <strong>clear</strong>()</code></div>
                            <div class="summary">
                                <p>
                                    Removes all entries from the hash table.
                                </p>
                            </div>
                        </li>
                        <li class="method">
                            <div class="methodsignature"><code>Boolean <strong>isEmpty</strong>()</code></div>
                            <div class="summary">
                                <p>
                                    Returns true if the hash table contains no key/value pairs.
                                </p>
                            </div>
                        </li>
                        <li class="method">
                            <div class="methodsignature"><code>Array <strong>keys</strong>()</code></div>
                            <div class="summary">
                                <p>
                                    Returns an array containing all the keys contained in the hash table.
                                </p>
                            </div>
                        </li>
                        <li class="method">
                            <div class="methodsignature"><code>Array <strong>values</strong>()</code></div>
                            <div class="summary">
                                <p>
                                    Returns an array containing all the values contained in the hash table.
                                </p>
                            </div>
                        </li>
                        <li class="method">
                            <div class="methodsignature"><code>Array <strong>entries</strong>()</code></div>
                            <p class="new">New in version 2.0</p>
                            <div class="summary">
                                <p>
                                    Returns an array containing all the entries contained in the hash table. Each entry
                                    is a two element array containing the key and value respectively for that entry.
                                </p>
                            </div>
                        </li>
                        <li class="method">
                            <div class="methodsignature"><code>void <strong>remove</strong>(Object
                                <em>key</em>)</code></div>
                            <div class="summary">
                                <p class="new">Updated in version 2.0: now returns the value associated with the removed
                                    key</p>
                                <p>
                                    Removes the key and its corresponding value from the hash table.
                                </p>
                            </div>
                        </li>
                        <li class="method">
                            <div class="methodsignature"><code>Number <strong>size</strong>()</code></div>
                            <div class="summary">
                                <p>
                                    Returns the number of key/value pairs contained in the hash table.
                                </p>
                            </div>
                        </li>
                        <li class="method">
                            <div class="methodsignature"><code>Hashtable <strong>clone</strong>()</code></div>
                            <p class="new">New in version 2.0</p>
                            <div class="summary">
                                <p>
                                    Creates and returns a shallow copy of the hash table. If hashing and equality
                                    functions were provided to the hash table when it was constructed, they are passed
                                    into the new hash table.
                                </p>
                            </div>
                        </li>
                        <li class="method">
                            <div class="methodsignature"><code>void <strong>each</strong>(Function
                                <em>callback</em>)</code></div>
                            <p class="new">New in version 2.0</p>
                            <div class="summary">
                                <p>
                                    Iterates over all the entries in the hash table, calling the <code>callback</code>
                                    function for each entry. This function is passed two parameters:
                                </p>
                                <ul>
                                    <li><code>key</code>: the key for the current entry;</li>
                                    <li><code>value</code>: the value for the current entry.</li>
                                </ul>
                            </div>
                        </li>
                    </ul>
                    <p class="linktotop">
                        <a href="#container">Top</a>
                    </p>
                </div>
            </div>
            <div id="footer">
                <span class="externallinkinfo">
                    <strong>NB.</strong> All external links open in a new window.
                </span>
                Written by Tim Down. <a href="mailto:tim@timdown.co.uk">tim@timdown.co.uk</a>
                <br />
                jshashtable is distributed under the <a href="http://www.apache.org/licenses/LICENSE-2.0.html"
                    title="Apache License, Version 2.0 (opens in new window)" target="_blank">Apache License,
                    Version 2.0</a>
            </div>
        </div>
    </body>
</html>
